library(dplyr)
library(ggfortify)
library(tidyverse)
library(factoextra)
library(cluster)
library(mclust)
                   __           __ 
   ____ ___  _____/ /_  _______/ /_
  / __ `__ \/ ___/ / / / / ___/ __/
 / / / / / / /__/ / /_/ (__  ) /_  
/_/ /_/ /_/\___/_/\__,_/____/\__/   version 6.1.1
Type 'citation("mclust")' for citing this R package in publications.

Attaching package: ‘mclust’

The following object is masked from ‘package:purrr’:

    map

Exercise 1 (k-means clustering)

Consider data set lab15.

lab15 = read_delim("lab15.csv", delim = ",")
Rows: 120 Columns: 2
── Column specification ───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Delimiter: ","
dbl (2): x, y

ℹ Use `spec()` to retrieve the full column specification for this data.
ℹ Specify the column types or set `show_col_types = FALSE` to quiet this message.

Use k-means clustering with 2 clusters (with other parameters having default values) to cluster the data.

set.seed(20241212)

ex1.1 = kmeans(lab15, 2)

ex1.1
K-means clustering with 2 clusters of sizes 58, 62

Cluster means:
         x         y
1 2.385596 -1.421775
2 2.876544  2.760950

Clustering vector:
  [1] 2 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 1 1 1 2 2 1 1 2 1 1 2 2 2 1 2 2 2 1 2 2 2 1 2 2 1 1 1 2 2 1 1 2 2 1 2 2 1 1 1 2 1 1 2 2 2 1 1 2 1 1 2
 [70] 2 2 1 1 2 1 1 2 2 2 1 1 2 2 1 2 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 1 1 2 2 2 1 1 2 1 1

Within cluster sum of squares by cluster:
[1] 297.9516 408.2059
 (between_SS / total_SS =  42.9 %)

Available components:

[1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss" "betweenss"    "size"         "iter"         "ifault"      

Produce corresponding graph with factoextra::fviz_cluster().

ex1.1$tot.withinss
[1] 706.1574

What is the value of the objective function (in the component tot.withinss)

ex1.1$tot.withinss

Repeat the previous step until you find a different clustering of data. Visualize it. Which of the two clustering results is better?

# Repeat clustering to find a different clustering
kmeans_2_diff <- kmeans(lab15, centers = 2, nstart = 20)

# Visualize the new clustering
fviz_cluster(kmeans_2_diff, data = lab15)


# Compare objective function values
kmeans_2_diff$tot.withinss
[1] 656.0803

Find the values of tot.withinss for 2,3,…,10 clusters (using nstart=20 to find a good clustering). Use elbow method to find a good candidate for the total number of clusters to use.

# Compute tot.withinss for k = 2 to 10
tot_withinss <- map_dbl(2:10, function(k) {
  kmeans(lab15, centers = k, nstart = 20)$tot.withinss
})

# Elbow plot
plot(2:10, tot_withinss, type = "b", pch = 19, col = "blue", 
     xlab = "Number of Clusters", ylab = "Total Within-cluster Sum of Squares")

Visualize the results for the best number of clusters.

# Repeat clustering to find a different clustering
kmeans_4_diff <- kmeans(lab15, centers = 4, nstart = 20)

# Visualize the new clustering
fviz_cluster(kmeans_4_diff, data = lab15)

kmeans_4_diff$tot.withinss
[1] 221.7143

Compute average silhouette values for 2,…,10 clusters and produce plot of average silhouette values. Which number of clusters gives the maximal value?

silhouette_avg <- map_dbl(2:10, function(k) {
  km <- kmeans(lab15, centers = k, nstart = 20)
  sil <- silhouette(km$cluster, dist(lab15))
  mean(sil[, 3])
})

# Plot silhouette values
plot(2:10, silhouette_avg, type = "b", pch = 19, col = "red", 
     xlab = "Number of Clusters", ylab = "Average Silhouette Width")

Consider data set USArrests. Find the best clustering (based on elbow method) for the dataset without scaling variables.

# K-means clustering (elbow method)
tot_withinss_usa <- map_dbl(2:10, function(k) {
  kmeans(USArrests, centers = k, nstart = 20)$tot.withinss
})
plot(2:10, tot_withinss_usa, type = "b", pch = 19, col = "blue",
     xlab = "Number of Clusters", ylab = "Total Within-cluster Sum of Squares")


# Visualization with respect to Murder and Assault
best_k <- 3
km_usarrests <- kmeans(USArrests, centers = best_k, nstart = 20)
fviz_cluster(km_usarrests, data = USArrests, choose.vars = c("Murder", "Assault"))

Visualize the results with respect to Murder and Assault variables.

# Visualization with respect to Murder and Assault
best_k <- 3
km_usarrests <- kmeans(USArrests, centers = best_k, nstart = 20)
fviz_cluster(km_usarrests, data = USArrests, choose.vars = c("Murder", "Assault"))

Find the best clustering for the scaled data set. Which clusters would you consider to be more meaningful?

# Scale data
usarrests_scaled <- scale(USArrests)

# K-means clustering on scaled data
tot_withinss_scaled <- map_dbl(2:10, function(k) {
  kmeans(usarrests_scaled, centers = k, nstart = 20)$tot.withinss
})
plot(2:10, tot_withinss_scaled, type = "b", pch = 19, col = "blue",
     xlab = "Number of Clusters", ylab = "Total Within-cluster Sum of Squares")

# Best clustering
best_k_scaled <- 4
km_scaled <- kmeans(usarrests_scaled, centers = best_k_scaled, nstart = 20)
fviz_cluster(km_scaled, data = usarrests_scaled)

Hierarchical clustering In the case of Hierarchical clustering we get sequence of nested clusters and we have to decide, how many clusters to use. For deciding which number of clusters to use, we can look at dendogram (at which height there is the largest gap with no additional clusters appearing) or to use some measure like silhouette for choosing a good number of clusters.The result depends heavily on the dissimilarity measure used.

Exercise 2 (hierarcical clustering)

Consider data set lab15. Let us use the Euclidean distance (which can be computed by dist() function) for the dissimilarity measure.

Apply hierarchical clustering to the data set with complete linkage and look at the dendrogram. Can you spot a good number of clusters from it?

# Compute distance matrix and perform clustering
dist_lab15 <- dist(lab15)
hclust_complete <- hclust(dist_lab15, method = "complete")

# Plot dendrogram
plot(hclust_complete, labels = FALSE, main = "Complete Linkage Dendrogram")
rect.hclust(hclust_complete, k = 3, border = "red")

Visualize the resulting clusters.

clusters_hc <- cutree(hclust_complete, k = 3)
fviz_cluster(list(data = lab15, cluster = clusters_hc))

Compute average silhouettes for cluster sizes 2,3,…,10. Which number of clusters gives the highest value?

silhouette_avg_hc <- map_dbl(2:10, function(k) {
  clusters <- cutree(hclust_complete, k = k)
  sil <- silhouette(clusters, dist_lab15)
  mean(sil[, 3])
})

Visualize the resulting clusters for the chosen number of clusters.

# Plot silhouette values
plot(2:10, silhouette_avg_hc, type = "b", pch = 19, col = "red",
     xlab = "Number of Clusters", ylab = "Average Silhouette Width")

best_k_hc <- 4
clusters_hc <- cutree(hclust_complete, k = best_k_hc)
fviz_cluster(list(data = lab15, cluster = clusters_hc))

Exercise 3 (effect of metric in hierarchical clustering)

Consider the data set ISLR::NCI60. Let us use hierarchical clustering with average linkage.

Find the best number of clusters for the data based on average silhouette when scaled data and Euclidean distance is used. Use table(cancer_types,assigned_clusters) to see if some cancer types correspond well to the discovered clusters.


nci_scaled <- scale(ISLR::NCI60$data)

# Perform hierarchical clustering
dist_nci <- dist(nci_scaled)
hc_avg <- hclust(dist_nci, method = "average")

# Silhouette method
silhouette_avg_nci <- map_dbl(2:10, function(k) {
  clusters <- cutree(hc_avg, k = k)
  sil <- silhouette(clusters, dist_nci)
  mean(sil[, 3])
})
plot(2:10, silhouette_avg_nci, type = "b", pch = 19, col = "red",
     xlab = "Number of Clusters", ylab = "Average Silhouette Width")

best_k_hc <- 2
clusters_hc <- cutree(hc_avg, k = best_k_hc)
fviz_cluster(list(data = nci_scaled, cluster = clusters_hc))

Repeat the previous step in the case of correlation based dissimilarity matrix (defined by as.dist(1-cor(t(data_df))))). Which approach seems to be better?

# Correlation-based distance
dist_corr <- as.dist(1 - cor(t(nci_scaled)))

# Perform hierarchical clustering
hc_corr <- hclust(dist_corr, method = "average")

# Silhouette method
silhouette_avg_corr <- map_dbl(2:10, function(k) {
  clusters <- cutree(hc_corr, k = k)
  sil <- silhouette(clusters, dist_corr)
  mean(sil[, 3])
})
plot(2:10, silhouette_avg_corr, type = "b", pch = 19, col = "blue",
     xlab = "Number of Clusters", ylab = "Average Silhouette Width")

best_k_hc <- 8
clusters_hc <- cutree(dist_corr, k = best_k_hc)
Error in tree$merge : $ operator is invalid for atomic vectors

Clustering by Gaussian Mixture model The idea of Gaussian mixture distribution is to assume that data is a random sample from objects of different types/classes and that observation values in each class are normally distributed. It is possible to allow different degrees for flexibility for distributions of different types of observations - can only means be different or can there be some kind of differences in the covariance matrices also. The command Mclust(), when used with default parameters, chooses the flexibility of the distributions and the number of clusters by using BIC.

Exercise 4 (Soft clustering by Gaussian mixture model)

Consider again the dataset lab15.

Use MClust() to determine the best number of clusters. Look also at the plot of BIC values (those are negative of usual BIC values we have used before) by using the plot() command with the parameter what=“BIC”. Visualize the clustering results by fviz_cluster() and also by plot() with the option what=“classification”. Look also at the estimated probabilities of the 49th observation to belong to different clusters. Which are the two most probable clusters for this observation? Hint: the cluster probabilities can be obtained by predict() command.

# Fit Gaussian mixture model
gmm_lab15 <- Mclust(lab15)
fitting ...

  |                                                                                                                                          
  |                                                                                                                                    |   0%
  |                                                                                                                                          
  |=                                                                                                                                   |   1%
  |                                                                                                                                          
  |==                                                                                                                                  |   2%
  |                                                                                                                                          
  |===                                                                                                                                 |   2%
  |                                                                                                                                          
  |====                                                                                                                                |   3%
  |                                                                                                                                          
  |=====                                                                                                                               |   4%
  |                                                                                                                                          
  |======                                                                                                                              |   5%
  |                                                                                                                                          
  |=======                                                                                                                             |   6%
  |                                                                                                                                          
  |========                                                                                                                            |   6%
  |                                                                                                                                          
  |=========                                                                                                                           |   7%
  |                                                                                                                                          
  |==========                                                                                                                          |   8%
  |                                                                                                                                          
  |===========                                                                                                                         |   9%
  |                                                                                                                                          
  |============                                                                                                                        |   9%
  |                                                                                                                                          
  |==============                                                                                                                      |  10%
  |                                                                                                                                          
  |===============                                                                                                                     |  11%
  |                                                                                                                                          
  |================                                                                                                                    |  12%
  |                                                                                                                                          
  |=================                                                                                                                   |  13%
  |                                                                                                                                          
  |==================                                                                                                                  |  13%
  |                                                                                                                                          
  |===================                                                                                                                 |  14%
  |                                                                                                                                          
  |====================                                                                                                                |  15%
  |                                                                                                                                          
  |=====================                                                                                                               |  16%
  |                                                                                                                                          
  |======================                                                                                                              |  17%
  |                                                                                                                                          
  |=======================                                                                                                             |  17%
  |                                                                                                                                          
  |========================                                                                                                            |  18%
  |                                                                                                                                          
  |=========================                                                                                                           |  19%
  |                                                                                                                                          
  |==========================                                                                                                          |  20%
  |                                                                                                                                          
  |===========================                                                                                                         |  20%
  |                                                                                                                                          
  |============================                                                                                                        |  21%
  |                                                                                                                                          
  |=============================                                                                                                       |  22%
  |                                                                                                                                          
  |==============================                                                                                                      |  23%
  |                                                                                                                                          
  |===============================                                                                                                     |  24%
  |                                                                                                                                          
  |================================                                                                                                    |  24%
  |                                                                                                                                          
  |=================================                                                                                                   |  25%
  |                                                                                                                                          
  |==================================                                                                                                  |  26%
  |                                                                                                                                          
  |===================================                                                                                                 |  27%
  |                                                                                                                                          
  |====================================                                                                                                |  28%
  |                                                                                                                                          
  |=====================================                                                                                               |  28%
  |                                                                                                                                          
  |======================================                                                                                              |  29%
  |                                                                                                                                          
  |=======================================                                                                                             |  30%
  |                                                                                                                                          
  |=========================================                                                                                           |  31%
  |                                                                                                                                          
  |==========================================                                                                                          |  31%
  |                                                                                                                                          
  |===========================================                                                                                         |  32%
  |                                                                                                                                          
  |============================================                                                                                        |  33%
  |                                                                                                                                          
  |=============================================                                                                                       |  34%
  |                                                                                                                                          
  |==============================================                                                                                      |  35%
  |                                                                                                                                          
  |===============================================                                                                                     |  35%
  |                                                                                                                                          
  |================================================                                                                                    |  36%
  |                                                                                                                                          
  |=================================================                                                                                   |  37%
  |                                                                                                                                          
  |==================================================                                                                                  |  38%
  |                                                                                                                                          
  |===================================================                                                                                 |  39%
  |                                                                                                                                          
  |====================================================                                                                                |  39%
  |                                                                                                                                          
  |=====================================================                                                                               |  40%
  |                                                                                                                                          
  |======================================================                                                                              |  41%
  |                                                                                                                                          
  |=======================================================                                                                             |  42%
  |                                                                                                                                          
  |========================================================                                                                            |  43%
  |                                                                                                                                          
  |=========================================================                                                                           |  43%
  |                                                                                                                                          
  |==========================================================                                                                          |  44%
  |                                                                                                                                          
  |===========================================================                                                                         |  45%
  |                                                                                                                                          
  |============================================================                                                                        |  46%
  |                                                                                                                                          
  |=============================================================                                                                       |  46%
  |                                                                                                                                          
  |==============================================================                                                                      |  47%
  |                                                                                                                                          
  |===============================================================                                                                     |  48%
  |                                                                                                                                          
  |================================================================                                                                    |  49%
  |                                                                                                                                          
  |=================================================================                                                                   |  50%
  |                                                                                                                                          
  |===================================================================                                                                 |  50%
  |                                                                                                                                          
  |====================================================================                                                                |  51%
  |                                                                                                                                          
  |=====================================================================                                                               |  52%
  |                                                                                                                                          
  |======================================================================                                                              |  53%
  |                                                                                                                                          
  |=======================================================================                                                             |  54%
  |                                                                                                                                          
  |========================================================================                                                            |  54%
  |                                                                                                                                          
  |=========================================================================                                                           |  55%
  |                                                                                                                                          
  |==========================================================================                                                          |  56%
  |                                                                                                                                          
  |===========================================================================                                                         |  57%
  |                                                                                                                                          
  |============================================================================                                                        |  57%
  |                                                                                                                                          
  |=============================================================================                                                       |  58%
  |                                                                                                                                          
  |==============================================================================                                                      |  59%
  |                                                                                                                                          
  |===============================================================================                                                     |  60%
  |                                                                                                                                          
  |================================================================================                                                    |  61%
  |                                                                                                                                          
  |=================================================================================                                                   |  61%
  |                                                                                                                                          
  |==================================================================================                                                  |  62%
  |                                                                                                                                          
  |===================================================================================                                                 |  63%
  |                                                                                                                                          
  |====================================================================================                                                |  64%
  |                                                                                                                                          
  |=====================================================================================                                               |  65%
  |                                                                                                                                          
  |======================================================================================                                              |  65%
  |                                                                                                                                          
  |=======================================================================================                                             |  66%
  |                                                                                                                                          
  |========================================================================================                                            |  67%
  |                                                                                                                                          
  |=========================================================================================                                           |  68%
  |                                                                                                                                          
  |==========================================================================================                                          |  69%
  |                                                                                                                                          
  |===========================================================================================                                         |  69%
  |                                                                                                                                          
  |=============================================================================================                                       |  70%
  |                                                                                                                                          
  |==============================================================================================                                      |  71%
  |                                                                                                                                          
  |===============================================================================================                                     |  72%
  |                                                                                                                                          
  |================================================================================================                                    |  72%
  |                                                                                                                                          
  |=================================================================================================                                   |  73%
  |                                                                                                                                          
  |==================================================================================================                                  |  74%
  |                                                                                                                                          
  |===================================================================================================                                 |  75%
  |                                                                                                                                          
  |====================================================================================================                                |  76%
  |                                                                                                                                          
  |=====================================================================================================                               |  76%
  |                                                                                                                                          
  |======================================================================================================                              |  77%
  |                                                                                                                                          
  |=======================================================================================================                             |  78%
  |                                                                                                                                          
  |========================================================================================================                            |  79%
  |                                                                                                                                          
  |=========================================================================================================                           |  80%
  |                                                                                                                                          
  |==========================================================================================================                          |  80%
  |                                                                                                                                          
  |===========================================================================================================                         |  81%
  |                                                                                                                                          
  |============================================================================================================                        |  82%
  |                                                                                                                                          
  |=============================================================================================================                       |  83%
  |                                                                                                                                          
  |==============================================================================================================                      |  83%
  |                                                                                                                                          
  |===============================================================================================================                     |  84%
  |                                                                                                                                          
  |================================================================================================================                    |  85%
  |                                                                                                                                          
  |=================================================================================================================                   |  86%
  |                                                                                                                                          
  |==================================================================================================================                  |  87%
  |                                                                                                                                          
  |===================================================================================================================                 |  87%
  |                                                                                                                                          
  |====================================================================================================================                |  88%
  |                                                                                                                                          
  |=====================================================================================================================               |  89%
  |                                                                                                                                          
  |======================================================================================================================              |  90%
  |                                                                                                                                          
  |========================================================================================================================            |  91%
  |                                                                                                                                          
  |=========================================================================================================================           |  91%
  |                                                                                                                                          
  |==========================================================================================================================          |  92%
  |                                                                                                                                          
  |===========================================================================================================================         |  93%
  |                                                                                                                                          
  |============================================================================================================================        |  94%
  |                                                                                                                                          
  |=============================================================================================================================       |  94%
  |                                                                                                                                          
  |==============================================================================================================================      |  95%
  |                                                                                                                                          
  |===============================================================================================================================     |  96%
  |                                                                                                                                          
  |================================================================================================================================    |  97%
  |                                                                                                                                          
  |=================================================================================================================================   |  98%
  |                                                                                                                                          
  |==================================================================================================================================  |  98%
  |                                                                                                                                          
  |=================================================================================================================================== |  99%
  |                                                                                                                                          
  |====================================================================================================================================| 100%
# BIC plot
plot(gmm_lab15, what = "BIC")


# Visualize clustering
fviz_cluster(gmm_lab15)

plot(gmm_lab15, what = "classification")


# Probabilities for the 49th observation
predicted_probs <- predict(gmm_lab15)
predicted_probs$z[49, ] # Probabilities for observation 49
           1            2            3            4            5 
5.210224e-01 5.749146e-04 5.785793e-06 4.783969e-01 8.839710e-10 
LS0tCnRpdGxlOiAiTGFiMTUiCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCmBgYHtyfQpsaWJyYXJ5KGRwbHlyKQpsaWJyYXJ5KGdnZm9ydGlmeSkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoZmFjdG9leHRyYSkKbGlicmFyeShjbHVzdGVyKQpsaWJyYXJ5KG1jbHVzdCkKYGBgCgojIyBFeGVyY2lzZSAxIChrLW1lYW5zIGNsdXN0ZXJpbmcpCkNvbnNpZGVyIGRhdGEgc2V0IGxhYjE1LgoKYGBge3J9CmxhYjE1ID0gcmVhZF9kZWxpbSgibGFiMTUuY3N2IiwgZGVsaW0gPSAiLCIpCmBgYAoKVXNlIGstbWVhbnMgY2x1c3RlcmluZyB3aXRoIDIgY2x1c3RlcnMgKHdpdGggb3RoZXIgcGFyYW1ldGVycyBoYXZpbmcgZGVmYXVsdCB2YWx1ZXMpIHRvIGNsdXN0ZXIgdGhlIGRhdGEuIAoKYGBge3J9CnNldC5zZWVkKDIwMjQxMjEyKQoKZXgxLjEgPSBrbWVhbnMobGFiMTUsIDIpCgpleDEuMQpgYGAKCgpQcm9kdWNlIGNvcnJlc3BvbmRpbmcgZ3JhcGggd2l0aCBmYWN0b2V4dHJhOjpmdml6X2NsdXN0ZXIoKS4gCgpgYGB7cn0KZmFjdG9leHRyYTo6ZnZpel9jbHVzdGVyKGV4MS4xLCBsYWIxNSkKYGBgCgoKV2hhdCBpcyB0aGUgdmFsdWUgb2YgdGhlIG9iamVjdGl2ZSBmdW5jdGlvbiAoaW4gdGhlIGNvbXBvbmVudCB0b3Qud2l0aGluc3MpCmBgYHtyfQpleDEuMSR0b3Qud2l0aGluc3MKYGBgCgpSZXBlYXQgdGhlIHByZXZpb3VzIHN0ZXAgdW50aWwgeW91IGZpbmQgYSBkaWZmZXJlbnQgY2x1c3RlcmluZyBvZiBkYXRhLiBWaXN1YWxpemUgaXQuIFdoaWNoIG9mIHRoZSB0d28gY2x1c3RlcmluZyByZXN1bHRzIGlzIGJldHRlcj8KCmBgYHtyfQojIFJlcGVhdCBjbHVzdGVyaW5nIHRvIGZpbmQgYSBkaWZmZXJlbnQgY2x1c3RlcmluZwprbWVhbnNfMl9kaWZmIDwtIGttZWFucyhsYWIxNSwgY2VudGVycyA9IDIsIG5zdGFydCA9IDIwKQoKIyBWaXN1YWxpemUgdGhlIG5ldyBjbHVzdGVyaW5nCmZ2aXpfY2x1c3RlcihrbWVhbnNfMl9kaWZmLCBkYXRhID0gbGFiMTUpCmBgYAoKCmBgYHtyfQojIENvbXBhcmUgb2JqZWN0aXZlIGZ1bmN0aW9uIHZhbHVlcwprbWVhbnNfMl9kaWZmJHRvdC53aXRoaW5zcwpgYGAKCgpGaW5kIHRoZSB2YWx1ZXMgb2YgdG90LndpdGhpbnNzIGZvciAyLDMs4oCmLDEwIGNsdXN0ZXJzICh1c2luZyBuc3RhcnQ9MjAgdG8gZmluZCBhIGdvb2QgY2x1c3RlcmluZykuIFVzZSBlbGJvdyBtZXRob2QgdG8gZmluZCBhIGdvb2QgY2FuZGlkYXRlIGZvciB0aGUgdG90YWwgbnVtYmVyIG9mIGNsdXN0ZXJzIHRvIHVzZS4gCgoKCmBgYHtyfQojIENvbXB1dGUgdG90LndpdGhpbnNzIGZvciBrID0gMiB0byAxMAp0b3Rfd2l0aGluc3MgPC0gbWFwX2RibCgyOjEwLCBmdW5jdGlvbihrKSB7CiAga21lYW5zKGxhYjE1LCBjZW50ZXJzID0gaywgbnN0YXJ0ID0gMjApJHRvdC53aXRoaW5zcwp9KQoKIyBFbGJvdyBwbG90CnBsb3QoMjoxMCwgdG90X3dpdGhpbnNzLCB0eXBlID0gImIiLCBwY2ggPSAxOSwgY29sID0gImJsdWUiLCAKICAgICB4bGFiID0gIk51bWJlciBvZiBDbHVzdGVycyIsIHlsYWIgPSAiVG90YWwgV2l0aGluLWNsdXN0ZXIgU3VtIG9mIFNxdWFyZXMiKQoKYGBgCgoKVmlzdWFsaXplIHRoZSByZXN1bHRzIGZvciB0aGUgYmVzdCBudW1iZXIgb2YgY2x1c3RlcnMuCgpgYGB7cn0KIyBSZXBlYXQgY2x1c3RlcmluZyB0byBmaW5kIGEgZGlmZmVyZW50IGNsdXN0ZXJpbmcKa21lYW5zXzRfZGlmZiA8LSBrbWVhbnMobGFiMTUsIGNlbnRlcnMgPSA0LCBuc3RhcnQgPSAyMCkKCiMgVmlzdWFsaXplIHRoZSBuZXcgY2x1c3RlcmluZwpmdml6X2NsdXN0ZXIoa21lYW5zXzRfZGlmZiwgZGF0YSA9IGxhYjE1KQpgYGAKCmBgYHtyfQprbWVhbnNfNF9kaWZmJHRvdC53aXRoaW5zcwpgYGAKCgpDb21wdXRlIGF2ZXJhZ2Ugc2lsaG91ZXR0ZSB2YWx1ZXMgZm9yIDIs4oCmLDEwIGNsdXN0ZXJzIGFuZCBwcm9kdWNlIHBsb3Qgb2YgYXZlcmFnZSBzaWxob3VldHRlIHZhbHVlcy4gV2hpY2ggbnVtYmVyIG9mIGNsdXN0ZXJzIGdpdmVzIHRoZSBtYXhpbWFsIHZhbHVlPwoKYGBge3J9CnNpbGhvdWV0dGVfYXZnIDwtIG1hcF9kYmwoMjoxMCwgZnVuY3Rpb24oaykgewogIGttIDwtIGttZWFucyhsYWIxNSwgY2VudGVycyA9IGssIG5zdGFydCA9IDIwKQogIHNpbCA8LSBzaWxob3VldHRlKGttJGNsdXN0ZXIsIGRpc3QobGFiMTUpKQogIG1lYW4oc2lsWywgM10pCn0pCgojIFBsb3Qgc2lsaG91ZXR0ZSB2YWx1ZXMKcGxvdCgyOjEwLCBzaWxob3VldHRlX2F2ZywgdHlwZSA9ICJiIiwgcGNoID0gMTksIGNvbCA9ICJyZWQiLCAKICAgICB4bGFiID0gIk51bWJlciBvZiBDbHVzdGVycyIsIHlsYWIgPSAiQXZlcmFnZSBTaWxob3VldHRlIFdpZHRoIikKCmBgYAoKCkNvbnNpZGVyIGRhdGEgc2V0IFVTQXJyZXN0cy4KRmluZCB0aGUgYmVzdCBjbHVzdGVyaW5nIChiYXNlZCBvbiBlbGJvdyBtZXRob2QpIGZvciB0aGUgZGF0YXNldCB3aXRob3V0IHNjYWxpbmcgdmFyaWFibGVzLiAKCmBgYHtyfQojIEstbWVhbnMgY2x1c3RlcmluZyAoZWxib3cgbWV0aG9kKQp0b3Rfd2l0aGluc3NfdXNhIDwtIG1hcF9kYmwoMjoxMCwgZnVuY3Rpb24oaykgewogIGttZWFucyhVU0FycmVzdHMsIGNlbnRlcnMgPSBrLCBuc3RhcnQgPSAyMCkkdG90LndpdGhpbnNzCn0pCnBsb3QoMjoxMCwgdG90X3dpdGhpbnNzX3VzYSwgdHlwZSA9ICJiIiwgcGNoID0gMTksIGNvbCA9ICJibHVlIiwKICAgICB4bGFiID0gIk51bWJlciBvZiBDbHVzdGVycyIsIHlsYWIgPSAiVG90YWwgV2l0aGluLWNsdXN0ZXIgU3VtIG9mIFNxdWFyZXMiKQpgYGAKCgoKClZpc3VhbGl6ZSB0aGUgcmVzdWx0cyB3aXRoIHJlc3BlY3QgdG8gTXVyZGVyIGFuZCBBc3NhdWx0IHZhcmlhYmxlcy4KCmBgYHtyfQojIFZpc3VhbGl6YXRpb24gd2l0aCByZXNwZWN0IHRvIE11cmRlciBhbmQgQXNzYXVsdApiZXN0X2sgPC0gMwprbV91c2FycmVzdHMgPC0ga21lYW5zKFVTQXJyZXN0cywgY2VudGVycyA9IGJlc3RfaywgbnN0YXJ0ID0gMjApCmZ2aXpfY2x1c3RlcihrbV91c2FycmVzdHMsIGRhdGEgPSBVU0FycmVzdHMsIGNob29zZS52YXJzID0gYygiTXVyZGVyIiwgIkFzc2F1bHQiKSkKYGBgCgoKRmluZCB0aGUgYmVzdCBjbHVzdGVyaW5nIGZvciB0aGUgc2NhbGVkIGRhdGEgc2V0LiBXaGljaCBjbHVzdGVycyB3b3VsZCB5b3UgY29uc2lkZXIgdG8gYmUgbW9yZSBtZWFuaW5nZnVsPwoKYGBge3J9CiMgU2NhbGUgZGF0YQp1c2FycmVzdHNfc2NhbGVkIDwtIHNjYWxlKFVTQXJyZXN0cykKCiMgSy1tZWFucyBjbHVzdGVyaW5nIG9uIHNjYWxlZCBkYXRhCnRvdF93aXRoaW5zc19zY2FsZWQgPC0gbWFwX2RibCgyOjEwLCBmdW5jdGlvbihrKSB7CiAga21lYW5zKHVzYXJyZXN0c19zY2FsZWQsIGNlbnRlcnMgPSBrLCBuc3RhcnQgPSAyMCkkdG90LndpdGhpbnNzCn0pCnBsb3QoMjoxMCwgdG90X3dpdGhpbnNzX3NjYWxlZCwgdHlwZSA9ICJiIiwgcGNoID0gMTksIGNvbCA9ICJibHVlIiwKICAgICB4bGFiID0gIk51bWJlciBvZiBDbHVzdGVycyIsIHlsYWIgPSAiVG90YWwgV2l0aGluLWNsdXN0ZXIgU3VtIG9mIFNxdWFyZXMiKQoKYGBgCgoKYGBge3J9CiMgQmVzdCBjbHVzdGVyaW5nCmJlc3Rfa19zY2FsZWQgPC0gNAprbV9zY2FsZWQgPC0ga21lYW5zKHVzYXJyZXN0c19zY2FsZWQsIGNlbnRlcnMgPSBiZXN0X2tfc2NhbGVkLCBuc3RhcnQgPSAyMCkKZnZpel9jbHVzdGVyKGttX3NjYWxlZCwgZGF0YSA9IHVzYXJyZXN0c19zY2FsZWQpCmBgYAoKCkhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nCkluIHRoZSBjYXNlIG9mIEhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIHdlIGdldCBzZXF1ZW5jZSBvZiBuZXN0ZWQgY2x1c3RlcnMgYW5kIHdlIGhhdmUgdG8gZGVjaWRlLCBob3cgbWFueSBjbHVzdGVycyB0byB1c2UuIEZvciBkZWNpZGluZyB3aGljaCBudW1iZXIgb2YgY2x1c3RlcnMgdG8gdXNlLCB3ZSBjYW4gbG9vayBhdCBkZW5kb2dyYW0gKGF0IHdoaWNoIGhlaWdodCB0aGVyZSBpcyB0aGUgbGFyZ2VzdCBnYXAgd2l0aCBubyBhZGRpdGlvbmFsIGNsdXN0ZXJzIGFwcGVhcmluZykgb3IgdG8gdXNlIHNvbWUgbWVhc3VyZSBsaWtlIHNpbGhvdWV0dGUgZm9yIGNob29zaW5nIGEgZ29vZCBudW1iZXIgb2YgY2x1c3RlcnMuVGhlIHJlc3VsdCBkZXBlbmRzIGhlYXZpbHkgb24gdGhlIGRpc3NpbWlsYXJpdHkgbWVhc3VyZSB1c2VkLgoKIyMgRXhlcmNpc2UgMiAoaGllcmFyY2ljYWwgY2x1c3RlcmluZykKCkNvbnNpZGVyIGRhdGEgc2V0IGxhYjE1LiBMZXQgdXMgdXNlIHRoZSBFdWNsaWRlYW4gZGlzdGFuY2UgKHdoaWNoIGNhbiBiZSBjb21wdXRlZCBieSBkaXN0KCkgZnVuY3Rpb24pIGZvciB0aGUgZGlzc2ltaWxhcml0eSBtZWFzdXJlLgoKQXBwbHkgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgdG8gdGhlIGRhdGEgc2V0IHdpdGggY29tcGxldGUgbGlua2FnZSBhbmQgbG9vayBhdCB0aGUgZGVuZHJvZ3JhbS4gQ2FuIHlvdSBzcG90IGEgZ29vZCBudW1iZXIgb2YgY2x1c3RlcnMgZnJvbSBpdD8KCmBgYHtyfQojIENvbXB1dGUgZGlzdGFuY2UgbWF0cml4IGFuZCBwZXJmb3JtIGNsdXN0ZXJpbmcKZGlzdF9sYWIxNSA8LSBkaXN0KGxhYjE1KQpoY2x1c3RfY29tcGxldGUgPC0gaGNsdXN0KGRpc3RfbGFiMTUsIG1ldGhvZCA9ICJjb21wbGV0ZSIpCgojIFBsb3QgZGVuZHJvZ3JhbQpwbG90KGhjbHVzdF9jb21wbGV0ZSwgbGFiZWxzID0gRkFMU0UsIG1haW4gPSAiQ29tcGxldGUgTGlua2FnZSBEZW5kcm9ncmFtIikKcmVjdC5oY2x1c3QoaGNsdXN0X2NvbXBsZXRlLCBrID0gMywgYm9yZGVyID0gInJlZCIpCgpgYGAKCgpWaXN1YWxpemUgdGhlIHJlc3VsdGluZyBjbHVzdGVycy4KCmBgYHtyfQpjbHVzdGVyc19oYyA8LSBjdXRyZWUoaGNsdXN0X2NvbXBsZXRlLCBrID0gMykKZnZpel9jbHVzdGVyKGxpc3QoZGF0YSA9IGxhYjE1LCBjbHVzdGVyID0gY2x1c3RlcnNfaGMpKQpgYGAKCgpDb21wdXRlIGF2ZXJhZ2Ugc2lsaG91ZXR0ZXMgZm9yIGNsdXN0ZXIgc2l6ZXMgMiwzLOKApiwxMC4gV2hpY2ggbnVtYmVyIG9mIGNsdXN0ZXJzIGdpdmVzIHRoZSBoaWdoZXN0IHZhbHVlPwoKYGBge3J9CnNpbGhvdWV0dGVfYXZnX2hjIDwtIG1hcF9kYmwoMjoxMCwgZnVuY3Rpb24oaykgewogIGNsdXN0ZXJzIDwtIGN1dHJlZShoY2x1c3RfY29tcGxldGUsIGsgPSBrKQogIHNpbCA8LSBzaWxob3VldHRlKGNsdXN0ZXJzLCBkaXN0X2xhYjE1KQogIG1lYW4oc2lsWywgM10pCn0pCgpgYGAKCgpWaXN1YWxpemUgdGhlIHJlc3VsdGluZyBjbHVzdGVycyBmb3IgdGhlIGNob3NlbiBudW1iZXIgb2YgY2x1c3RlcnMuCgpgYGB7cn0KIyBQbG90IHNpbGhvdWV0dGUgdmFsdWVzCnBsb3QoMjoxMCwgc2lsaG91ZXR0ZV9hdmdfaGMsIHR5cGUgPSAiYiIsIHBjaCA9IDE5LCBjb2wgPSAicmVkIiwKICAgICB4bGFiID0gIk51bWJlciBvZiBDbHVzdGVycyIsIHlsYWIgPSAiQXZlcmFnZSBTaWxob3VldHRlIFdpZHRoIikKCmBgYAoKYGBge3J9CmJlc3Rfa19oYyA8LSA0CmNsdXN0ZXJzX2hjIDwtIGN1dHJlZShoY2x1c3RfY29tcGxldGUsIGsgPSBiZXN0X2tfaGMpCmZ2aXpfY2x1c3RlcihsaXN0KGRhdGEgPSBsYWIxNSwgY2x1c3RlciA9IGNsdXN0ZXJzX2hjKSkKCmBgYAoKCiMjIEV4ZXJjaXNlIDMgKGVmZmVjdCBvZiBtZXRyaWMgaW4gaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcpCkNvbnNpZGVyIHRoZSBkYXRhIHNldCBJU0xSOjpOQ0k2MC4gTGV0IHVzIHVzZSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZyB3aXRoIGF2ZXJhZ2UgbGlua2FnZS4KCkZpbmQgdGhlIGJlc3QgbnVtYmVyIG9mIGNsdXN0ZXJzIGZvciB0aGUgZGF0YSBiYXNlZCBvbiBhdmVyYWdlIHNpbGhvdWV0dGUgd2hlbiBzY2FsZWQgZGF0YSBhbmQgRXVjbGlkZWFuIGRpc3RhbmNlIGlzIHVzZWQuIFVzZSB0YWJsZShjYW5jZXJfdHlwZXMsYXNzaWduZWRfY2x1c3RlcnMpIHRvIHNlZSBpZiBzb21lIGNhbmNlciB0eXBlcyBjb3JyZXNwb25kIHdlbGwgdG8gdGhlIGRpc2NvdmVyZWQgY2x1c3RlcnMuCgpgYGB7cn0KCm5jaV9zY2FsZWQgPC0gc2NhbGUoSVNMUjo6TkNJNjAkZGF0YSkKCiMgUGVyZm9ybSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZwpkaXN0X25jaSA8LSBkaXN0KG5jaV9zY2FsZWQpCmhjX2F2ZyA8LSBoY2x1c3QoZGlzdF9uY2ksIG1ldGhvZCA9ICJhdmVyYWdlIikKCiMgU2lsaG91ZXR0ZSBtZXRob2QKc2lsaG91ZXR0ZV9hdmdfbmNpIDwtIG1hcF9kYmwoMjoxMCwgZnVuY3Rpb24oaykgewogIGNsdXN0ZXJzIDwtIGN1dHJlZShoY19hdmcsIGsgPSBrKQogIHNpbCA8LSBzaWxob3VldHRlKGNsdXN0ZXJzLCBkaXN0X25jaSkKICBtZWFuKHNpbFssIDNdKQp9KQpwbG90KDI6MTAsIHNpbGhvdWV0dGVfYXZnX25jaSwgdHlwZSA9ICJiIiwgcGNoID0gMTksIGNvbCA9ICJyZWQiLAogICAgIHhsYWIgPSAiTnVtYmVyIG9mIENsdXN0ZXJzIiwgeWxhYiA9ICJBdmVyYWdlIFNpbGhvdWV0dGUgV2lkdGgiKQoKYGBgCgpgYGB7cn0KYmVzdF9rX2hjIDwtIDIKY2x1c3RlcnNfaGMgPC0gY3V0cmVlKGhjX2F2ZywgayA9IGJlc3Rfa19oYykKZnZpel9jbHVzdGVyKGxpc3QoZGF0YSA9IG5jaV9zY2FsZWQsIGNsdXN0ZXIgPSBjbHVzdGVyc19oYykpCmBgYAoKClJlcGVhdCB0aGUgcHJldmlvdXMgc3RlcCBpbiB0aGUgY2FzZSBvZiBjb3JyZWxhdGlvbiBiYXNlZCBkaXNzaW1pbGFyaXR5IG1hdHJpeCAoZGVmaW5lZCBieSBhcy5kaXN0KDEtY29yKHQoZGF0YV9kZikpKSkpLiBXaGljaCBhcHByb2FjaCBzZWVtcyB0byBiZSBiZXR0ZXI/CgpgYGB7cn0KIyBDb3JyZWxhdGlvbi1iYXNlZCBkaXN0YW5jZQpkaXN0X2NvcnIgPC0gYXMuZGlzdCgxIC0gY29yKHQobmNpX3NjYWxlZCkpKQoKIyBQZXJmb3JtIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nCmhjX2NvcnIgPC0gaGNsdXN0KGRpc3RfY29yciwgbWV0aG9kID0gImF2ZXJhZ2UiKQoKIyBTaWxob3VldHRlIG1ldGhvZApzaWxob3VldHRlX2F2Z19jb3JyIDwtIG1hcF9kYmwoMjoxMCwgZnVuY3Rpb24oaykgewogIGNsdXN0ZXJzIDwtIGN1dHJlZShoY19jb3JyLCBrID0gaykKICBzaWwgPC0gc2lsaG91ZXR0ZShjbHVzdGVycywgZGlzdF9jb3JyKQogIG1lYW4oc2lsWywgM10pCn0pCnBsb3QoMjoxMCwgc2lsaG91ZXR0ZV9hdmdfY29yciwgdHlwZSA9ICJiIiwgcGNoID0gMTksIGNvbCA9ICJibHVlIiwKICAgICB4bGFiID0gIk51bWJlciBvZiBDbHVzdGVycyIsIHlsYWIgPSAiQXZlcmFnZSBTaWxob3VldHRlIFdpZHRoIikKCmBgYAoKYGBge3J9CmJlc3Rfa19oYyA8LSA4CmNsdXN0ZXJzX2hjIDwtIGN1dHJlZShkaXN0X2NvcnIsIGsgPSBiZXN0X2tfaGMpCmZ2aXpfY2x1c3RlcihsaXN0KGRhdGEgPSBuY2lfc2NhbGVkLCBjbHVzdGVyID0gY2x1c3RlcnNfaGMpKQpgYGAKCgpDbHVzdGVyaW5nIGJ5IEdhdXNzaWFuIE1peHR1cmUgbW9kZWwKVGhlIGlkZWEgb2YgR2F1c3NpYW4gbWl4dHVyZSBkaXN0cmlidXRpb24gaXMgdG8gYXNzdW1lIHRoYXQgZGF0YSBpcyBhIHJhbmRvbSBzYW1wbGUgZnJvbSBvYmplY3RzIG9mIGRpZmZlcmVudCB0eXBlcy9jbGFzc2VzIGFuZCB0aGF0IG9ic2VydmF0aW9uIHZhbHVlcyBpbiBlYWNoIGNsYXNzIGFyZSBub3JtYWxseSBkaXN0cmlidXRlZC4gSXQgaXMgcG9zc2libGUgdG8gYWxsb3cgZGlmZmVyZW50IGRlZ3JlZXMgZm9yIGZsZXhpYmlsaXR5IGZvciBkaXN0cmlidXRpb25zIG9mIGRpZmZlcmVudCB0eXBlcyBvZiBvYnNlcnZhdGlvbnMgLSBjYW4gb25seSBtZWFucyBiZSBkaWZmZXJlbnQgb3IgY2FuIHRoZXJlIGJlIHNvbWUga2luZCBvZiBkaWZmZXJlbmNlcyBpbiB0aGUgY292YXJpYW5jZSBtYXRyaWNlcyBhbHNvLiBUaGUgY29tbWFuZCBNY2x1c3QoKSwgd2hlbiB1c2VkIHdpdGggZGVmYXVsdCBwYXJhbWV0ZXJzLCBjaG9vc2VzIHRoZSBmbGV4aWJpbGl0eSBvZiB0aGUgZGlzdHJpYnV0aW9ucyBhbmQgdGhlIG51bWJlciBvZiBjbHVzdGVycyBieSB1c2luZyBCSUMuCgojIyBFeGVyY2lzZSA0IChTb2Z0IGNsdXN0ZXJpbmcgYnkgR2F1c3NpYW4gbWl4dHVyZSBtb2RlbCkKQ29uc2lkZXIgYWdhaW4gdGhlIGRhdGFzZXQgbGFiMTUuCgpVc2UgTUNsdXN0KCkgdG8gZGV0ZXJtaW5lIHRoZSBiZXN0IG51bWJlciBvZiBjbHVzdGVycy4gTG9vayBhbHNvIGF0IHRoZSBwbG90IG9mIEJJQyB2YWx1ZXMgKHRob3NlIGFyZSBuZWdhdGl2ZSBvZiB1c3VhbCBCSUMgdmFsdWVzIHdlIGhhdmUgdXNlZCBiZWZvcmUpIGJ5IHVzaW5nIHRoZSBwbG90KCkgY29tbWFuZCB3aXRoIHRoZSBwYXJhbWV0ZXIgd2hhdD0iQklDIi4KVmlzdWFsaXplIHRoZSBjbHVzdGVyaW5nIHJlc3VsdHMgYnkgZnZpel9jbHVzdGVyKCkgYW5kIGFsc28gYnkgcGxvdCgpIHdpdGggdGhlIG9wdGlvbiB3aGF0PSJjbGFzc2lmaWNhdGlvbiIuIExvb2sgYWxzbyBhdCB0aGUgZXN0aW1hdGVkIHByb2JhYmlsaXRpZXMgb2YgdGhlIDQ5dGggb2JzZXJ2YXRpb24gdG8gYmVsb25nIHRvIGRpZmZlcmVudCBjbHVzdGVycy4gV2hpY2ggYXJlIHRoZSB0d28gbW9zdCBwcm9iYWJsZSBjbHVzdGVycyBmb3IgdGhpcyBvYnNlcnZhdGlvbj8gSGludDogdGhlIGNsdXN0ZXIgcHJvYmFiaWxpdGllcyBjYW4gYmUgb2J0YWluZWQgYnkgcHJlZGljdCgpIGNvbW1hbmQuCgpgYGB7cn0KIyBGaXQgR2F1c3NpYW4gbWl4dHVyZSBtb2RlbApnbW1fbGFiMTUgPC0gTWNsdXN0KGxhYjE1KQoKIyBCSUMgcGxvdApwbG90KGdtbV9sYWIxNSwgd2hhdCA9ICJCSUMiKQoKIyBWaXN1YWxpemUgY2x1c3RlcmluZwpmdml6X2NsdXN0ZXIoZ21tX2xhYjE1KQpwbG90KGdtbV9sYWIxNSwgd2hhdCA9ICJjbGFzc2lmaWNhdGlvbiIpCgojIFByb2JhYmlsaXRpZXMgZm9yIHRoZSA0OXRoIG9ic2VydmF0aW9uCnByZWRpY3RlZF9wcm9icyA8LSBwcmVkaWN0KGdtbV9sYWIxNSkKcHJlZGljdGVkX3Byb2JzJHpbNDksIF0gIyBQcm9iYWJpbGl0aWVzIGZvciBvYnNlcnZhdGlvbiA0OQoKYGBgCgo=